package SubjectTree.Three;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

import Utility.TreeNode;

public class FindBottomLeftValue {

/**
 * 难度：中等
 * 
 * 513. 找树左下角的值
 * 	给定一个二叉树，在树的最后一行找到最左边的值。
 * 	
 * 示例 1:
 * 	输入:
 * 	    2
 * 	   / \
 * 	  1   3
 * 	输出:
 * 	1
 * 	
 * 示例 2:
 * 	输入:
 * 	        1
 * 	       / \
 * 	      2   3
 * 	     /   / \
 * 	    4   5   6
 * 	       /
 * 	      7
 * 	输出:
 * 	7
 * 	
 * 注意: 您可以假设树（即给定的根节点）不为 NULL。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FindBottomLeftValue fblv = new FindBottomLeftValue();
		System.out.println(fblv.findBottomLeftValue2(TreeNode.MkTree("[3,1,5,0,2,4,6]")));
	}
	//自己写(逐层遍历)
	public int findBottomLeftValue(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		deque.offer(root);
		Map<Integer,Integer> map = new HashMap<>();
		//记录当前层数
		int floor = 1;
		while(!deque.isEmpty()) {
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				//把当前层数的第一个数(即最左边的数)放进map集合
				map.put(floor, map.getOrDefault(floor, node.val));
				if(node.left!=null) {
					deque.offer(node.left);
				}
				if(node.right!=null) {
					deque.offer(node.right);
				}
			}
			floor++;
		}
		return map.get(floor-1);
    }
	//自己写(递归)
	public int findBottomLeftValue_1(TreeNode root) {
		Map<Integer,Integer> map = new HashMap<>();
		int floor = 0;
		traversal_1(root,map,floor);
		for(int i:map.keySet()) {
			if(i>floor)floor=i;
		}
		return map.get(floor);
    }
	public void traversal_1(TreeNode root,Map<Integer,Integer> map,int floor) {
		if(root==null) return;
		floor++;
		traversal_1(root.left,map,floor);
		traversal_1(root.right,map,floor);
		map.put(floor, map.getOrDefault(floor, root.val));
	}
	//方法一：递归
	int maxLen = 0;
    int maxleftValue;
    public int findBottomLeftValue1(TreeNode root) {
        traversal1(root, 0);
        return maxleftValue;
    }
    private void traversal1(TreeNode root, int leftLen) {
        if (root.left == null && root.right == null) {
            if (leftLen > maxLen) {
                maxLen = leftLen;
                maxleftValue = root.val;
            }
            return;
        }
        if (root.left!=null) {
            leftLen++;
            traversal1(root.left, leftLen);
            leftLen--; // 回溯
        }
        if (root.right!=null) {
            leftLen++;
            traversal1(root.right, leftLen);
            leftLen--; // 回溯 
        }
        return;
    }
    //方法二：逐层遍历
    public int findBottomLeftValue2(TreeNode root) {
        Deque<TreeNode> que  = new LinkedList<>();
        if (root != null) que.offer(root);
        int result = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                if (i == 0) result = node.val; // 记录最后一行第一个元素
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
        }
        return result;
    }
}
